/// Source : https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
/// Author : bianwangyang
/// Time   : 2024-04-29
// 28. 找出字符串中第一个匹配项的下标
// 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
// 如果 needle 不是 haystack 的一部分，则返回  -1 。
#include <iostream>

using namespace std;
// BF算法
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        int i = 0, j = 0;
        while(i < n && j < m) {
            if(haystack[i] == needle[j]) {
                i++; j++;
            } else {
                i = i - j + 1;  // i 回退到原i的下一个位置
                j = 0;          // j 从0开始
            }
        }
        if(j >= m) return i - m;
        else return -1;
    }
};


int main() {
    cout << Solution().strStr("sadbutsad", "sad") << endl;  // 0
    cout << Solution().strStr("leetcode", "leeto") << endl; // -1

    return 0;
}